Hard disk drives are well known and commonly used storage devices. Accordingly, although the present invention is not limited for use with hard disk drives, they will be used to illustrate the background of the invention and problems associated with the prior art.
A host computer is typically connected to a hard disk drive by a small computer system interface (SCSI) bus. Hard disk drives generally include one or more hard disks, a read/write head and a controller. In the most basic systems, the host computer sends a series of SCSI read commands to the hard disk drive's controller in response to the requirements of an application program. After each command, the requisite data is located on the disk, retrieved and sent to the host over the SCSI bus. Significant overhead, or data delivery latencies, are built into this basic system. In other words, the data stream to the host computer may be interrupted due to "housekeeping" activities and data seeking.
On the host side, these latencies include the time period between the reading of the last data byte and the sending of last data byte over the SCSI bus, the time period between the sending of the last data byte and "bus free," the time period required for the host to execute the next SCSI data request and the time period required for the host to arbitrate for the bus and send the last command byte. When data required by the host application is not contiguously located on the disk, disk side overhead includes the time required to move the head to a new track and the time required for the requisite portion of the disk to rotate to the head.
Caching data in fast memory is one way of improving the performance of computer systems. Caching involves transferring data from a storage device to a faster random access cache memory. If data required by the application program is not in the cache memory, then the storage device is accessed, thereby causing the application to wait. Such situations are referred to as cache misses.
Predictive caching is a method of reducing the number of instances where data required by the application program must be retrieved from the storage device instead of the cache memory. Predictive caching programs are sometimes stored in the firmware associated with the storage device's controller. One common predictive caching method is known as the "read ahead" caching scheme. The "read ahead" caching scheme simply involves reading data from the next sector on the current cylinder after information is read from the current sector. Obviously, the "read ahead" scheme is most effective where large amounts of data are contiguously stored within the storage device. There are, however, a number applications where blocks of data from many different locations within the storage device must be sequentially accessed. Here, the aforementioned data delivery latencies are experienced each time there is a cache miss because the next data block is not located in the next storage area within the storage device.
One application that is not well suited for "read ahead" predictive caching schemes is video editing. Video editing systems often require three data streams, two audio and one video. The audio data streams require 96 Kbytes/sec, while the video data stream requires 3.6 Mbytes/sec. In video editing systems, such as the Lightworks System by Lightworks Editing Systems Ltd., located in London, England, an edit decision list (EDL) is produced which describes the order that the audio and video clips will be mixed. The EDL is essentially an access schedule listing various blocks of data within the storage device. Unfortunately, this data is rarely contiguously stored within the storage device. In order to accommodate the data stream requirements, prior art video editing systems have employed host-based data caching schemes in which large amounts of audio and video data can be stored. Such host-based cache management techniques require a buffer having at least 32 Mbytes of costly random access memory. Such memory can add thousands of dollars to the retail cost of the system. In addition, the host CPU must be used to manage the host based cache memory.
Accordingly, a need exists for a caching scheme which is capable of supplying an uninterrupted stream of non-contiguously stored data to the host, but which does not require large amounts of expensive random access memory.